from collections import defaultdict, deque, Counter
from functools import lru_cache, reduce
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
from random import randint
from math import *
import operator
import sys
from itertools import accumulate
hpop = heappop
hpush = heappush
MOD = 10**9 + 7
input=sys.stdin.readline
def solution():
n = int(input())
arr = list(map(int, input().split()))
m = int(input())
max_num = max(arr)
sm_factor = [0]*(max_num + 1)
for i in range(2, max_num + 1):
if sm_factor[i] == 0:
for j in range(i, max_num + 1, i):
if sm_factor[j] == 0 :
sm_factor[j] = i
prime_freq = [0]*(max_num + 1)
for val in arr:
t = sm_factor[val]
while t:
while val % t == 0:
val //= t
prime_freq[t] += 1
t = sm_factor[val]
for i in range(1, len(prime_freq)):
prime_freq[i] += prime_freq[i-1]
for _ in range(m):
l,r = map(int, input().split())
if l >= len(prime_freq):
print(0)
else:
if r >= len(prime_freq): r = -1
print(prime_freq[r] - prime_freq[l-1])
def main():
t = 1
for _ in range(t):
solution()
main()
//بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيمِ
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template<typename T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define Samo7a ios_base::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);
#define re return
#define FX(n) fixed << setprecision(n)
#define endl '\n'
#define sz(v) (int) v.size()
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define pb push_back
#define eb emplace_back
#define pi acos(-1)
#define F first
#define S second
const int N = 1e7 + 10, MOD = 1e9 + 7;
const int dx[]{1, -1, 0, 0, 1, -1, 1, -1};
const int dy[]{0, 0, 1, -1, 1, -1, -1, 1};
inline void debugMode() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
//الشَّيْطَانُ يَعِدُكُمُ الْفَقْرَ وَيَأْمُرُكُم بِالْفَحْشَاءِ ۖ وَاللَّهُ يَعِدُكُم مَّغْفِرَةً مِّنْهُ وَفَضْلًا ۗ وَاللَّهُ وَاسِعٌ عَلِيمٌ (268)
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
ll divi[1LL * N];
int f[1LL * N];
void seive() {
bitset<N> is_prime;
is_prime.set();
is_prime[0] = 0, is_prime[1] = 0;
for (int i = 2; i<= 1e7; i++) {
if (not is_prime[i])
continue;
for (int j = i; j <= 1e7; j += i) {
if (i != j)
is_prime[j] = 0;
divi[i] += f[j];
}
}
}
void TestCase() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
f[x]++;
}
seive();
for (int i = 1; i < N; i++)
divi[i] += divi[i - 1];
int m;
cin >> m;
while (m--) {
int l, r;
cin >> l >> r;
l = min((int) 1e7, l), r = min((int) 1e7, r);
cout << divi[r] - divi[l - 1] << endl;
}
}
int main() {
Samo7a
debugMode();
int t = 1;
//cin >> t;
while (t--) {
TestCase();
}
re 0;
}320A - Magic Numbers | 1658A - Marin and Photoshoot |
514A - Chewbaсca and Number | 382A - Ksenia and Pan Scales |
734B - Anton and Digits | 1080A - Petya and Origami |
1642D - Repetitions Decoding | 1440A - Buy the String |
1658F - Juju and Binary String | 478A - Initial Bet |
981A - Antipalindrome | 365A - Good Number |
1204B - Mislove Has Lost an Array | 1409D - Decrease the Sum of Digits |
1476E - Pattern Matching | 1107A - Digits Sequence Dividing |
1348A - Phoenix and Balance | 1343B - Balanced Array |
1186A - Vus the Cossack and a Contest | 1494A - ABC String |
1606A - AB Balance | 1658C - Shinju and the Lost Permutation |
1547C - Pair Programming | 550A - Two Substrings |
797B - Odd sum | 1093A - Dice Rolling |
1360B - Honest Coach | 1399C - Boats Competition |
1609C - Complex Market Analysis | 1657E - Star MST |